GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

</head>

</header>

</div>

<th colspan="2" class="hintergrundfarbe6" style="font-size:105%;">FEAL

</th></tr>

<tr>

<td colspan="2" style="text-align:center;"><small>Die Rundenfunktion F von FEAL</small>

</td></tr>

<tr>

<td>Entwickler

</td>

<td>Akihiro Shimizu und Shoji Miyaguchi, beide von <a href="Nippon_Telegraph_and_Telephone" title="Nippon Telegraph and Telephone">NTT</a>

</td></tr>

<tr>

<td>Veröffentlicht

</td>

<td>FEAL-4 1987; FEAL-N/NX 1990

</td></tr>

<tr>

<td>Schlüssellänge

</td>

<td>64 Bit (FEAL), 128 Bits (FEAL-NX)

</td></tr>

<tr>

<td>Blockgröße

</td>

<td>64 Bit

</td></tr>

<tr>

<td>Struktur

</td>

<td><a href="Feistelchiffre" title="Feistelchiffre">Feistelchiffre</a>

</td></tr>

<tr>

<td>Runden

</td>

<td>Ursprünglich 4 bei FEAL-4, dann erweitert auf 8 Runden; FEAL-N/NX mit variabler Rundenanzahl, wobei minimal 32 empfohlen sind.

</td></tr>

<tr>

<th colspan="2" class="hintergrundfarbe6">Beste bekannte Kryptoanalyse

</th></tr>

<tr>

<td colspan="2" style="text-align:center;">FEAL-4 ist sehr anfällig für die <a href="Lineare_Kryptoanalyse" title="Lineare Kryptoanalyse">lineare Kryptoanalyse</a> mit nur fünf bekannten Klartextblöcken. (Matsui und Yamagishi, 1992).<br> FEAL-N/NX ist für die <a href="Differentielle_Kryptoanalyse" class="mw-redirect" title="Differentielle Kryptoanalyse">differentielle Kryptoanalyse</a> mit weniger als 31 Runden anfällig. (Biham und Shamir, 1991).

</td></tr></tbody></table>

<p><b>FEAL</b> (<i><b>F</b>ast Data <b>E</b>ncipherment <b>Al</b>gorithm</i>) ist eine <a href="Blockchiffre" class="mw-redirect" title="Blockchiffre">Blockchiffre</a> und zählt zu den <a href="Symmetrisches_Kryptosystem" title="Symmetrisches Kryptosystem">symmetrischen</a> <a href="Feistelchiffre" title="Feistelchiffre">Feistelchiffren</a>. Das Ziel bei der Entwicklung, die von dem japanischen Telefonkonzern <a href="Nippon_Telegraph_and_Telephone" title="Nippon Telegraph and Telephone">Nippon Telegraph and Telephone</a> (NTT) ausging, war, eine effiziente Implementierung eines Verschlüsselungsalgorithmus in Software auch für kleine <a href="Mikrocontroller" title="Mikrocontroller">Mikrocontroller</a> zu erreichen und damit eine Alternative zu dem von amerikanischen Behörden entwickelten <a href="Data_Encryption_Standard" title="Data Encryption Standard">Data Encryption Standard</a> (DES) zu schaffen. DES ist in Software nur vergleichsweise ineffizient zu implementieren.

</p><p>FEAL diente in den Jahren nach seiner Entwicklung 1987 vor allem als Testobjekt für verschiedenartige Angriffszenarien auf Verschlüsselungsalgorithmen. Insbesondere diente er dazu, die heute wesentlichen Analyseverfahren, die <a href="Differentielle_Kryptoanalyse" class="mw-redirect" title="Differentielle Kryptoanalyse">differentielle Kryptoanalyse</a> und die <a href="Lineare_Kryptoanalyse" title="Lineare Kryptoanalyse">lineare Kryptoanalyse</a>, in ihrer Entwicklung voranzubringen. FEAL selbst gilt, in den ursprünglichen Versionen wie FEAL-4 und FEAL-8, als gebrochen und sollte daher nicht eingesetzt werden.

</p>

<div class="mw-heading mw-heading2"><h2 id="Funktionsweise">Funktionsweise</h2></div>

<p>Der <a href="Datenblock" title="Datenblock">Datenblock</a> von 64 <a href="Bit" title="Bit">Bit</a> besteht aus zwei Wörtern <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fbbedf9f5f71ca52f8f24392c3cc18fca6c420dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.383ex; height:2.509ex;" alt="{\displaystyle L_{i}}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/db421291be9d0103404ced7495b363437b67b6b1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.564ex; height:2.509ex;" alt="{\displaystyle R_{i}}" loading="lazy"></span> zu je 32 Bit. Eine Feistelrunde besteht in der Auswertung der Rundenfunktion <i>F</i> (Bild) auf einem Wort und <a href="Kontravalenz" title="Kontravalenz">XOR-Verknüpfung</a> des Ergebnisses mit dem anderen Wort und anschließender Vertauschung der Wörter:

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{i+1}\!\,=R_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1742ddfdb21b367c476d435cc7c87884cbccae38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.145ex; height:2.509ex;" alt="{\displaystyle L_{i+1}\!\,=R_{i}}" loading="lazy"></span></dd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R_{i+1}\!\,=L_{i}\oplus F(R_{i},K_{i})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/31fc92050af9d7f25b1b01e4c8a2d1898067699b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.906ex; height:2.843ex;" alt="{\displaystyle R_{i+1}\!\,=L_{i}\oplus F(R_{i},K_{i})}" loading="lazy"></span></dd></dl>

<p>Die Funktion <i>F</i> zerlegt das Wort <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/db421291be9d0103404ced7495b363437b67b6b1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.564ex; height:2.509ex;" alt="{\displaystyle R_{i}}" loading="lazy"></span> in vier <a href="Byte" title="Byte">Byte</a>, die im Bild jeweils durch eine Linie symbolisiert werden, und erhält als Eingabe außerdem einen Rundenschlüssel <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/719736a1feb0bd7e73bb1425641a61229f55bb6d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.773ex; height:2.509ex;" alt="{\displaystyle K_{i}}" loading="lazy"></span> (2 Byte). Damit wird viermal eine bitweise <a href="Kontravalenz" title="Kontravalenz">XOR-Verknüpfung</a> von zwei Bytes angewandt, und je zweimal eine der Funktionen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{0}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ebe0ac45a38c4437bd2689a14ec434cd499e7e49.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{0}}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{1}}" loading="lazy"></span> ausgewertet, die zwei Eingabebytes auf ein Ausgabebyte abbilden. Sie addieren zunächst die beiden Eingabebytes modulo <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 256}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 256}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/efd966471b105b28988b60feb52a85e350ab5631.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.487ex; height:2.176ex;" alt="{\displaystyle 256}" loading="lazy"></span>, und im Fall von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{1}}" loading="lazy"></span> wird dazu noch 1 addiert, wodurch das Zwischenergebnis <i>h</i> entsteht. Dieses wird um zwei Bitpositionen nach links rotiert:

</p>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{i}(x,y)=(h\,{\bmod {\,}}64)\cdot 4+\lfloor h/64\rfloor ;\;h=(x+y+i)\,{\bmod {\,}}256}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1c81170d06d518bfddcd0c92c0511307b4bd7dfb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:61.99ex; height:2.843ex;" alt="{\displaystyle S_{i}(x,y)=(h\,{\bmod {\,}}64)\cdot 4+\lfloor h/64\rfloor ;\;h=(x+y+i)\,{\bmod {\,}}256}" loading="lazy"></span></dd></dl>

<p>Die Chiffre verwendet außerdem <a href="Key_Whitening" title="Key Whitening">Key Whitening</a> vor der ersten und nach der letzten Runde.

</p>

<div class="mw-heading mw-heading2"><h2 id="Versionen">Versionen</h2></div>

<p>Ursprünglich wurde 1988 von dem Entwicklerteam um Akihiro Shimizu und Shoji Miyaguchi bei NTT FEAL-4 entwickelt. Dieser <a href="Algorithmus" title="Algorithmus">Algorithmus</a> und seine Entstehungsgeschichte dokumentiert auch sehr anschaulich und mit teilweise amüsanten Abläufen die Probleme beim Entwickeln sicherer Blockverschlüsselungsalgorithmen.

</p><p>Damit der Algorithmus in Software einen möglichst hohen Durchsatz erzielt, war die Anzahl der Runden auf nur vier festgelegt. FEAL-4 wurde noch im gleichen Jahr 1988 auf der <i>Eurocrypt '88</i> von B. den Boer gebrochen.<sup id="cite_ref-boer_1-0" class="reference"><a href="#cite_note-boer-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Nur zwei Jahre später wurde von Sean Murphy die von ihm neu entwickelte differentielle Kryptoanalyse erfolgreich gegen FEAL-4 eingesetzt, wobei er nur 20 gewählte Klartextblöcke benötigte.<sup id="cite_ref-murphy_2-0" class="reference"><a href="#cite_note-murphy-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p><p>Die Entwickler verbesserten daraufhin im Jahr 1989 ihren Algorithmus, indem sie die Zahl der Runden auf acht erhöhten (FEAL-8). Dieser Algorithmus wurde ebenfalls im gleichen Jahr von <a href="Eli_Biham" title="Eli Biham">Biham</a> und <a href="Adi_Shamir" title="Adi Shamir">Shamir</a> auf der Konferenz <i>SECURICOM '89</i> erfolgreich kryptoanalysiert.

</p><p>Die Entwickler sahen sich daraufhin gezwungen, ihr Ziel, mit wenigen Runden eine effiziente Softwareimplementierung zu erreichen, endgültig aufzugeben, und veröffentlichten FEAL-N mit einer variablen Anzahl von Runden. Auf der <i>SECURICOM '91</i> konnte wieder von Biham und Shamir gezeigt werden, das FEAL-N mindestens 32 Runden benötigt, damit es nicht effizienter als durch eine <a href="Brute-Force-Methode" title="Brute-Force-Methode">Brute-Force-Suche</a> angegriffen werden kann.

</p><p>Die Entwickler von FEAL entwarfen parallel im Jahr 1990 auch FEAL-NX, eine Variante, die mit 128 Bit langen Schlüsseln statt der ursprünglichen 64-Bit-Schlüssel arbeitet. Sehr zum Leidwesen der Entwickler wurde auf der <i>SECURICOM '91</i> von Biham und Shamir gezeigt, dass FEAL-NX genauso leicht zu brechen ist wie FEAL-N mit 64-Bit-Schlüsseln.<sup id="cite_ref-biham_3-0" class="reference"><a href="#cite_note-biham-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p><p>Darüber hinaus wurden von verschiedenen Entwicklungsteams Modifikationen zur Stärkung vorgeschlagen, wie FEAL-N(X)S, welche FEAL durch eine dynamische Vertauschungsfunktion stärken soll. Allerdings gehen alle diese Erweiterungen sehr zu Lasten des Datendurchsatzes.

</p><p>FEAL wird vor allem zum Testen und Verfeinern von kryptoanalytischen Angriffsmethoden genutzt. FEAL sollte, egal in welcher Version, wegen seiner bekannten Schwächen nicht in sicherheitskritischen Bereichen eingesetzt werden. FEAL war in den USA patentiert, das Patent lief 2009 aus.

</p>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-boer-1"><span class="mw-cite-backlink"><a href="#cite_ref-boer_1-0">↑</a></span> <span class="reference-text">Bert den Boer: <cite style="font-style:italic">Cryptanalysis of F.E.A.L.</cite> In: <cite style="font-style:italic">Lecture Notes in Computer Science</cite>. 330. Jahrgang, 1988, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>293–299</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1007/3-540-45961-8_27">10.1007/3-540-45961-8_27</a></span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:FEAL&rft.atitle=Cryptanalysis+of+F.E.A.L.&rft.au=Bert%26%2332%3Bden+Boer&rft.btitle=Lecture+Notes+in+Computer+Science&rft.date=1988&rft.doi=10.1007%2F3-540-45961-8_27&rft.genre=book&rft.pages=293-299&rft.volume=330.+Jahrgang" style="display:none"> </span></span>

</li>

<li id="cite_note-murphy-2"><span class="mw-cite-backlink"><a href="#cite_ref-murphy_2-0">↑</a></span> <span class="reference-text">Sean Murphy: <cite style="font-style:italic">The cryptanalysis of FEAL-4 with 20 chosen plaintexts</cite>. In: <cite style="font-style:italic">Journal of Cryptology</cite>. 2. Jahrgang, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>3</span>, Januar 1990, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>145–155</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1007/BF00190801">10.1007/BF00190801</a></span> (<a rel="nofollow" class="external text" href="http://www.isg.rhul.ac.uk/~sean/feal.pdf">rhul.ac.uk</a> [PDF]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:FEAL&rft.atitle=The+cryptanalysis+of+FEAL-4+with+20+chosen+plaintexts&rft.au=Sean%26%2332%3BMurphy&rft.date=1990-01&rft.doi=10.1007%2FBF00190801&rft.genre=journal&rft.issue=3&rft.jtitle=Journal+of+Cryptology&rft.pages=145-155&rft.volume=2.+Jahrgang" style="display:none"> </span></span>

</li>

<li id="cite_note-biham-3"><span class="mw-cite-backlink"><a href="#cite_ref-biham_3-0">↑</a></span> <span class="reference-text">Eli Biham, Adi Shamir: <cite style="font-style:italic">Differential cryptanalysis of DES-like cryptosystems</cite>. In: <cite style="font-style:italic">Journal of Cryptology</cite>. 4. Jahrgang, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>1</span>, Januar 1991, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>3–72</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1007/BF00630563">10.1007/BF00630563</a></span> (<a rel="nofollow" class="external text" href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.31.2000&rep=rep1&type=pdf">psu.edu</a> [PDF]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:FEAL&rft.atitle=Differential+cryptanalysis+of+DES-like+cryptosystems&rft.au=Eli%26%2332%3BBiham%2C%26%2332%3BAdi+Shamir&rft.date=1991-01&rft.doi=10.1007%2FBF00630563&rft.genre=journal&rft.issue=1&rft.jtitle=Journal+of+Cryptology&rft.pages=3-72&rft.volume=4.+Jahrgang" style="display:none"> </span></span>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-04-25" href="https://de.wikipedia.org/wiki/?title=FEAL&oldid=255473533">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>